package util.linkedList.impl;

import util.linkedList.LinkedList;

/**
 * 双向链表
 *
 * @Author Huzz
 * @Created 2021-10-09 8:54
 */
public class DoubleLinkedList<T> implements LinkedList {
    /**
     * 表头
     */
    private Node<T> nodeHead;
    /**
     * 节点个数
     */
    private int nodeCount;

    /**
     * 构造函数
     */
    public DoubleLinkedList() {
        // 初始化链表, 创建表头(表头不存储数据)
        nodeHead = new Node<T>(null, null, null);
        // 初始化前驱和后继, 默认指向自身
        nodeHead.prev = nodeHead.next = nodeHead;
        // 初始化节点个数, 0个
        nodeCount = 0;
    }

    /**
     * 节点长度
     *
     * @return
     */
    @Override
    public int size() {
        return nodeCount;
    }

    /**
     * 返回链表是否为空
     *
     * @return 空:true | 非空:false
     */
    @Override
    public boolean isEmpty() {
        return nodeCount == 0;
    }

    /**
     * 获取第index位置的节点
     *
     * @param index
     * @return
     */
    private Node<T> getNode(int index) {
        if (index < 0 || index >= nodeCount) {
            throw new IndexOutOfBoundsException();
        }

        if (index <= nodeCount / 2) {
            /* 正向查找 */
            // 初始化指向第一个Node
            Node<T> node = nodeHead.next;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            /*反向查找*/
            // 初始化指向最后一个Node
            Node<T> rNode = nodeHead.prev;
            // 查找范围长度
            int rLength = nodeCount - index - 1;
            for (int j = 0; j < rLength; j++) {
                rNode = rNode.prev;
            }

            return rNode;
        }


    }

    /**
     * 获取第index位置的节点的值
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        return getNode(index).value;
    }

    /**
     * 获取第1个节点的值
     *
     * @return
     */
    @Override
    public T getFirst() {
        return getNode(0).value;
    }

    /**
     * 获取最后一个节点的值
     *
     * @return
     */
    @Override
    public T getLast() {
        return getNode(nodeCount - 1).value;
    }

    /**
     * 将节点插入到第index位置之前
     *
     * @param index
     * @param data
     */
    @Override
    public void insert(int index, Object data) {
        // 若初始化时除头节点外没有其他节点
        if (index == 0) {
            // 新建节点
            Node<T> node = new Node<>(nodeHead, nodeHead.next, (T) data);
            nodeHead.next = node;
            node.next.prev = node;
            nodeCount++;
            return;
        }

        Node<T> inode = getNode(index);
        Node<T> tNode = new Node<>(inode.prev, inode, (T) data);
        inode.prev.next = tNode;
        inode.prev = tNode;
        nodeCount++;
        return;
    }

    /**
     * 将节点插入第一个节点处
     *
     * @param data
     */
    @Override
    public void insertFirst(Object data) {
        insert(0, (T) data);
    }

    /**
     * 将节点追加到链表的末尾
     *
     * @param data
     */
    @Override
    public void append(Object data) {
        Node<T> node = new Node<>(nodeHead.prev, nodeHead, (T) data);
        nodeHead.prev.next = node;
        nodeHead.prev = node;

        nodeCount++;
    }

    /**
     * 删除index位置的节点
     *
     * @param index
     */
    @Override
    public void del(int index) {
        Node<T> node = getNode(index);
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node = null;
        nodeCount--;
    }

    /**
     * 删除第一个节点
     */
    @Override
    public void deleteFirst() {
        del(0);
    }

    /**
     * 删除最后一个节点
     */
    @Override
    public void deleteLast() {
        del(nodeCount - 1);
    }

    /** ======================================定义节点============================================== */
    /**
     * 双向链表节点定义
     *
     * @param <T>
     */
    private class Node<T> {
        // 前驱
        public Node prev;
        // 后继
        public Node next;
        // 数据
        public T value;

        public Node(Node prev, Node next, T data) {
            this.prev = prev;
            this.next = next;
            this.value = data;
        }
    }
    /** =========================================================================================== */
}
